//树可以看成是一个连通且 无环 的 无向 图。 
//
// 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信
//息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。 
//
// 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入: edges = [[1,2],[1,3],[2,3]]
//输出: [2,3]
// 
//
// 示例 2： 
//
// 
//
// 
//输入: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
//输出: [1,4]
// 
//
// 
//
// 提示: 
//
// 
// n == edges.length 
// 3 <= n <= 1000 
// edges[i].length == 2 
// 1 <= ai < bi <= edges.length 
// ai != bi 
// edges 中无重复元素 
// 给定的图是连通的 
// 
//
// 
//
// 
// 注意：本题与主站 684 题相同： https://leetcode-cn.com/problems/redundant-connection/ 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 👍 60 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2025-04-20 12:48:57
 * @description LCR 118.冗余连接
 */
public class SevenLpjUW{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 SevenLpjUW fun=new SevenLpjUW();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	//判断哪个点加入的时候使得这个图变成环了，就保存，每次都保存，最后那个答案
	//判断成环，可以用并查集，如果是单边的组合，就假设是有向图设置共同祖先，
	// 如果两个的祖先已经相同，会成环
	//然后为什么可以在第一次成环的时候就返回，因为第一次成环的边
	//就是环里最后一次出现的边
	public int[] findRedundantConnection1(int[][] edges) {
		int n = edges.length;
		int[] parent = new int[n + 1]; // 节点编号从 1 开始
		for (int i = 1; i <= n; i++) {
			parent[i] = i; // 初始化每个节点的父节点是自己
		}

		for (int[] edge : edges) {
			int u = edge[0], v = edge[1];
			int rootU = find(parent, u);
			int rootV = find(parent, v);
			if (rootU == rootV) {
				return edge; // 已经连通，说明这条边会形成环
			}
			parent[rootV] = rootU; // 合并两个连通分量
		}
		return new int[]{-1, -1}; // 无冗余边（题目保证有解，所以不会执行到这里）
	}

	private int find(int[] parent, int x) {
		if (parent[x] != x) {
			parent[x] = find(parent, parent[x]); // 路径压缩
		}
		return parent[x];
	}

	public int[] findRedundantConnection(int[][] edges) {
		// 邻接表 键为节点，值为相邻节点
		Map<Integer, List<Integer>> map = new HashMap<>();
		for (int[] edge : edges) {
			int n = edge[0];
			int m  = edge[1];

			//防治重复搜索已经dfs过的节点出现死循环
			Set<Integer> visited = new HashSet<>();

			//dfs 判断 n m 是否可以连同
			if(dfs(n,m,map,visited)){
				return edge;
			}

			if(!map.containsKey(n)){
				map.put(n,new ArrayList<>());
			}
			map.get(n).add(m);
			if(!map.containsKey(m)){
				map.put(m,new ArrayList<>());
			}
			map.get(m).add(n);
		}
		return new int[0];
	}

		private boolean dfs(int n, int m, Map<Integer, List<Integer>> map, Set<Integer> visited) {
			//同节点之间输出
			if (n==m)return true;

			visited.add(n);
			List<Integer> neighbors  = map.get(n);
			if (neighbors == null) return false;
			for (int i = 0; i < neighbors.size(); i++) {
				int neighbor = neighbors.get(i);
				if(!visited.contains(neighbor) && dfs(neighbor,m,map,visited)){
					return true;
				}
			}
			return false;
		}

}
//leetcode submit region end(Prohibit modification and deletion)

}
